package 动态规划.背包And分组And切割问题系列;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/17 8:43
 */
public class offer101分割等和子集 {


    /*
     提供 一下 这个题的拓展思路:
     1. 分成 k  个 子集, 每个子集 sum 为 target 分组方案!
     以及其他方面的拓展!
     */


    public static void main(String[] args) {
        System.out.println(20 >> 1 | 1);
    }




    /*
     转换一下, 成为 **组合求和** 题目的 思想,进行一个求解
     这个 题 只需要  找到一个 就行, 存在 ! 有点类似于 左程 云的 一个题, 就是  **xx游戏** , 也是返回true or false 的
     那个 可以break 的那个,
     */
    public boolean dp(int nums[]){
        int sum = Arrays.stream(nums).sum();
        if((sum & 1) == 1){
            return false;
        }
        Boolean dp[][] = new Boolean[nums.length + 1][sum /2 + 1];

        /*
         最终版本的 动态规划如下:
         */
        Arrays.fill(dp[nums.length],false);
        dp[nums.length][0] = true;
        for(int index = nums.length - 1;index >= 0; index--){
            dp[index][0] = true;
            for(int rest = 1;rest <= sum / 2;rest++){
                if(rest - nums[index] >= 0 && dp[index + 1][rest - nums[index]]){
                    dp[index][rest] = true;
                    continue;
                }
                dp[index][rest] = dp[index + 1][rest];
            }
        }
//        return recursion(0,sum >> 1,nums,dp);
        return dp[0][sum / 2];
    }


    public boolean recursion(int index,int rest,int nums[],Boolean dp[][]){
        if(rest == 0){
            return true;
        }
        if(index == nums.length){
            return false;
        }
        if(dp[index][rest] != null){
            return dp[index][rest];
        }
        boolean flag;
        // can choose  ,then choose
        if(rest - nums[index] >= 0 && recursion(index + 1,rest - nums[index],nums,dp)){
            return true;
        }
        // no choose
        flag = recursion(index + 1,rest,nums,dp);
        return dp[index][rest] = flag;
    }


    public boolean recursion(int index,int rest,int nums[]){
        if(rest == 0){
            return true;
        }
        if(index == nums.length){
            return false;
        }
        boolean flag = false;
        // can choose  ,then choose
        if(rest - nums[index] >= 0){
            flag = recursion(index + 1,rest - nums[index],nums);
        }
        // 可以 做一些 小小的 优化 , 直接将 下面的  判断语句给省掉!
        if(flag){
            return flag;
        }
        // no choose
        flag = recursion(index + 1,rest,nums);
        return flag;
    }









    /*
     这种思想是错的
     [1,1,2,2] 随便举个例子,都失败!
     */
    public boolean solution(int nums[]){
        int sum = Arrays.stream(nums).sum(),sum1 = 0;
        for(int i = 0;i < nums.length;i++){
            sum1 += nums[i];
            if(sum -sum1 == sum1){
                return true;
            }
        }
        return false;
    }
}
